Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n). If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.
For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.
Evaluate the sum of all the amicable numbers under 10000
In [9]:
# From euler-014
def find_factor(target)
result = []
(2..target).lazy.each do |i|
reminder = target % i
if reminder != 0
next
else
target = target / i
result << i
if target == 1
break
end
redo
end
end
return result
end
def find_divisor(num)
result = [1, num]
factors = find_factor(num)
(1..(factors.length - 1)).each do |i|
result << factors.combination(i).to_a.map{|set|set.inject(&:*)}
end
return result.flatten.uniq.sort
end
In [8]:
puts find_divisor(220)[0..-2].inject &:+
puts find_divisor(284)[0..-2].inject &:+
In [39]:
def find_amicable_numbers(n)
temp = find_divisor(n)[0..-2].inject &:+
verify = find_divisor(temp)[0..-2].inject &:+
return [n,temp] if verify == n and temp != n
return 0
end
In [40]:
results = []
(2..10000).each do |n|
temp = find_amicable_numbers(n)
results << temp if temp != 0
end
results
Out[40]:
In [41]:
results.flatten.uniq.inject &:+
Out[41]:
In [ ]: